Ant Colony Optimization and The Traveling salesman Problem

Ant Colony Optimization (ACO) for the Traveling Salesman Problem-Optimization Problem (TSP-OP)

I'm being specific saying TSP-OP instead of TSP, because TSP could refer to a decision or search problem, for example "Is there a path shorter than x" (YES/NO), or "find a path shorter than x" (PATH). Both of these have results which are trivial to validate. The problem here, TSP-OP, is non-trivial to validate, as knowing if the found path is the shortest is as difficult as the original problem. For TSP, we can't guarantee global minima unless performing a costly a brute force search.

The ACO algorithm is an algorithm that finds near optimal solutions for the TSP-OP. Yet we can't guarantee the global minima. The input for the algorithm is a graph and the weights for each edges, which here will be the euclidian distance between the nodes in the plane. The output will be the path and it's distance. The steps toward the solution can also be seen as an output, as the "certainty" of the algorithm is represented by how quick it finds the solution as well as the presence of multiple paths being marked (the vizualisation of this process can be seen in the animation below)

Defining functions

All code below has been fully and solely created by me (Gabriel Nilsson)

# Run this cell to install networkx and plotly library
# Alternatively run "pip install networkx" in your cmd promt
import sys
!{sys.executable} -m pip install networkx
!{sys.executable} -m pip install plotly

Importing Libraries

# For Visualizations
from plotly.subplots import make_subplots
from IPython.display import clear_output
from matplotlib.pyplot import figure
import plotly.graph_objects as go
import matplotlib.pyplot as plt
import plotly.express as px
from ipywidgets import *

# Library for manipulating graphs
import networkx as nx

# Functional libraries
import random as rnd
import numpy as np
import math
import time

Defining Functions for ACO

# Create Network
def CreateNetwork(amountNodes, createNew):
    # Create graph, position nodes randomly
    if createNew:
        G = nx.complete_graph(amountNodes)
        _pos = nx.random_layout(G)
    else:
        # Set graph and positions to global variables to copy last graph
        # Used when doing multiple simulations on the same graph
        G = network
        _pos = pos
        
    # Give each edge 2 attributes, weight and pheromone
    for edge in G.edges():
        startnode=edge[0] 
        endnode=edge[1]
        
        if createNew:
            # Set weight as euclidian distance according to pos
            distances = round(math.sqrt(((_pos[endnode][1]-_pos[startnode][1])**2)+
                            ((_pos[endnode][0]-_pos[startnode][0])**2)),2)
            # Set pheromones to 1
            G.add_edge(startnode, endnode, distance=distances, pheromone=1)
        else:
            # If not creating new, reset pheromones, distance will already be set
            G.add_edge(startnode, endnode, pheromone=1)
        
    # Return the network, and nodes positions
    return G, _pos

def GetRandomPathRec(path):
    # If path contains the whole network
    #     return
    if len(path) == len(network.nodes):
        return path
    
    # Continue from last node
    currentNode = path[-1]
    # Available neighbors 
    possibleNext = []
    # Neighbors individual probability weight for selection
    probArr = []
    
    # Append each available neighbor
    for neighbor in list(network[currentNode]):
        if neighbor not in path:
            possibleNext.append(neighbor)
            # Calculate individual prob using TraverseProb()
            probArr.append(TraverseProb(currentNode, neighbor))
    
    # Randomly select one neighbor
    selection = rnd.random() * sum(probArr)
    currI = -1
    while selection > 0:
        currI += 1
        selection -= probArr[currI]
    
    # Append selected neighbor
    path.append(possibleNext[currI])
    
    # Recursively return the rest of the path
    return GetRandomPathRec(path)

def LengthOfPath(path):
    # Calculate length of path
    length = 0
    # Increment with each distance of each edge
    for i in range(len(path)):
        length += network.edges[path[i], path[(i + 1) % len(path)]]['distance']
    return length

def IncrementPheromones(path, value):
    # Increment pheromone in each edge from path with value
    for i in range(len(path)):
        network.edges[path[i], path[(i + 1) % len(path)]]['pheromone'] += value

def TraverseProb(nodeA, nodeB):
    # distance^-distBias * pheromone^pheroBias
    # (-)distBias because more distance decrease probability
    # We want bias toward closer nodes
    return (pow(network.edges[nodeA, nodeB]['distance'], -distBias) * 
            pow(network.edges[nodeA, nodeB]['pheromone'], pheroBias))

Defining Functions for visualizations

# Draw the network
def DrawNetwork(pos, weights=[], text=""):
    # Set size bounds for displaying network
    figure(figsize=(10, 8), dpi=80)
    
    # get the phermone of each edge
    if weights == []:
        # If weights not given, get weights of current network
        weights = nx.get_edge_attributes(network, 'pheromone')
    
    # Width of edge correspond to relative pheromone level 
    widths = np.array(list(weights.values()))

    # Normalize widths
    widths /= max(widths)
    widths *= maxThickness
    
    # Get nodes
    nodelist = network.nodes()
    
    # Draw nodes
    nx.draw_networkx_nodes(network,pos,
                           nodelist=nodelist,
                           node_size=300,
                           node_color='red',
                           alpha=1)
    # Draw Edges
    nx.draw_networkx_edges(network,pos,
                           edgelist = weights.keys(),
                           width=widths,
                           edge_color='black',
                           alpha=1)
    
    # Draw digits on nodes
    nx.draw_networkx_labels(network, pos, font_size=10, font_color='white')
    
    # Update title
    if text:
        plt.title(text)
        
    plt.box(False)       
    plt.show()
    
def DisplayNetworkAnims(pos, index, snapshotInterval, doAnimation=True):
    # Update function for interactive animation (graph).
    # I put the Update function inside DisplayNetworkAnims() to get proper variable scope
    # as this function should only be accesible in this function
    def Update(step):
        DrawNetwork(pos, pheroHistories[index][step], 
                    f"Simulation {chr(index +65)}\nAnts simulated: {step * snapshotInterval}")
    
    if doAnimation:
        # Display animation
        for i in range(len(pheroHistories[index])):
            currentAnt = i * snapshotInterval # How many ants have been simulated at snapshot
            clear_output(wait=True)           # Clear output
            DrawNetwork(pos, pheroHistories[index][i], f"Ants simulated: {currentAnt}") # Redraw new graph
            time.sleep(.1) # Make it animate slowly
        time.sleep(1)
        clear_output(wait=True)

    # interact() creates a interactive slider connected to the fuunction Update
    print("You can click the slider and then use the left/right arrows to step through the process")
    interact(Update, step=widgets.IntSlider(min=0, max=len(pheroHistories[index]) - 1, step=1, value=0))

# Draws a line graph describing the performance of the algorithm
def PerformanceGraph(antLen, average, bestLen):
    # Create subplots depending on how many simulations have been performed (len(antLen) == amount of simulations)
    # Have 2 graphs per row if simulations > 1
    fig = make_subplots(rows=math.ceil(len(antLen) / 2), cols=1 if len(antLen) == 1 else 2)
    avgFig = px.scatter()
    
    # Boolean for displalying legend
    displayLegend = True
    
    for i in range(len(antLen)):
        # Only display legend for first graph
        if i == 1:
            displayLegend = False
        
        # Calculate current position among graphs
        rowPos = (i // 2) + 1
        colPos = i % 2 + 1

        # Set titles for each graph
        fig.update_yaxes(title_text="<b>Length of path</b><br>Unit is (100 km)s", row=rowPos, col=colPos)
        fig.update_xaxes(title_text="<b>Ants simulated</b>", row=rowPos, col=colPos)

        # Add trace for each line
        # Each ants traversed distance
        fig.add_trace(go.Scatter(y=antLen[i],
                            mode='lines',
                            name='Path length for each ant',
                            line_color='royalblue',
                            showlegend=displayLegend),
                      row = rowPos, col=colPos)
        
        # Shortest path so far
        fig.add_trace(go.Scatter(y=bestLen[i],
                            mode='lines',
                            name='Shortest path so far', 
                            line_color='lightgreen',
                            showlegend=displayLegend),
                      row = rowPos, col=colPos)
        
        # Critical termination line at 5% over the shortest path
        fig.add_trace(go.Scatter(y=np.array(bestLen[i])*(1+terminationLine),
                            name='5% over shortest path', 
                            line=dict(color='green', dash='dash'),
                            showlegend=displayLegend),
                      row = rowPos, col=colPos)
        
        # Filled green area for shortest length
        fig.add_trace(go.Scatter(
                            x=list(np.array(range(len(bestLen[i])))) + 
                                list(np.array(range(len(bestLen[i]))))[::-1],
                            y=list(np.array(bestLen[i])*(1+terminationLine))+list(np.array(bestLen[i]))[::-1],
                            fill='toself',
                            fillcolor='rgba(107,231,103,0.3)',
                            line_color='rgba(255,255,255,0)',
                            showlegend=displayLegend,
                            name='5% region'),
                      row = rowPos, col=colPos)
        
        # Running average of traversed distance
        fig.add_trace(go.Scatter(x=np.array(range(len(antLen[i]))) + runningAvgOf//2,
                                y=average[i],
                                mode='lines',
                                name=f'Running average of path length (average of {runningAvgOf} ants)', 
                                line_color='red',
                                showlegend=displayLegend),
                      row = rowPos, 
                      col=colPos)
        
        # Assign letter to each graph
        fig.add_annotation(text=chr(i + 65),
              xref="x domain", yref="y domain",
              x=0.95, y=0.95, showarrow=False, row = rowPos, col=colPos, font_size=25)
        
        # Only do running average graph if there are multiple simulations to compare
        if len(average) > 1:
            # avgFig is graph displaying each graphs running average
            avgFig.add_trace(go.Scatter(x=np.array(range(len(antLen[i]))) + runningAvgOf//2,
                                    y=average[i],
                                    mode='lines+text',
                                    name=f'Sim {chr(i + 65)} running average'))

    # Layout settings for performance graphs
    fig.update_layout(height=400*(math.ceil(len(antLen) / 2) + 1), 
                    width=1000, 
                    legend=dict(x=0, yanchor="bottom", y=-.15),
                    title_text='''<b>Linegraph showing performance of algorithm</b><br>
                                Distance of paths over amount of ants simulated''')
    fig.show()
    
    # Only do running average graph if there are multiple simulations to compare
    if len(average) > 1:
        # Set titles for running average graph
        avgFig.update_yaxes(title_text="<b>Running average of paths</b><br>Unit is (100 km)s")
        avgFig.update_xaxes(title_text="<b>Ants simulated</b>")
        avgFig.update_layout(title_text='''<b>Linegraph showing running average of path length 
                                        over amount of ants simulated</b>''')

        avgFig.show()

Algorithm

# Function for running ACO algorithm
def RunACO(nodesAmount,
            distBias,
            pheroBias,
            evaporationRate,
            pheromoneRate,
            simulations = 1,
            newNetwork=True):
    
    # It is in general a bad practice to make variables global, 
    # as that might lead to unintended access/interactions with the variables, 
    # which can lead to logical errors which are difficult to find.
    # I still choose to globalize these variables as to 
    # avoid being forced to tunnel them to the functions as parameters,
    # this increases the readability of the code
    global network
    global pos
    
    # These lists continuously store the relevant data for analysing the performance of the algorithm
    # I globalize these variables for same reason as stated above.
    global pheroHistories
    global maxThickness
    global antLenHistory
    global bestLenHistory
    global pheroHistory
    global runningAvg
    
    pheroHistories = []
    globAntLenHistory = []
    globBestLenHistory = []
    globRunningAvgHistory = []
    bestLengths = []
    bestPaths = []
    
    # Defining visual parameters
    # All data later visualized are stored every 'snapshotInterval' ant
    snapshotInterval=50
    # Max thickness of the lines in the network
    maxThickness = 8
    # Set fontsize for network visualization
    plt.rcParams.update({'font.size': 20})
    
    # Globalized termination line for same reason as stated above
    global terminationLine
    # When the running average distance of the ants hit the line which is 
    # 'terminationLine' % above the shortest distance, it terminates. (bestL * (1+terminationLine))
    terminationLine = .05
    
    # Set minimum amount of ants to simulate, in the beginning of the simulation, 
    # the termination condition might be fulfilled, as the best path so far can be very high.
    # Therefore we don't want to terminate if less than 'minimumAnts' have been smulated
    minimumAnts = 100
    # If the algorithm doesn't converge, we wish to terminate after 'maxAmountAnts' no matter what
    maxAmountAnts = 10000
    
    # A runningAvgOf 50 means that each value in the list runningAvg is the average of the 50 preceding values
    global runningAvgOf
    runningAvgOf=50
    
    # For each simulation
    for simiteration in range(simulations):
        
        # The current 'runningAvgOf' values to average
        # Works like a que, will be updated to always contain the most 
        # recent 'runningAvgOf' values from antLenHistory
        currentFocus = []

        # Storing pheromone values
        pheroHistory = []
        # Storing length of best path so far
        bestLenHistory = []
        # Storing length of each path created
        antLenHistory = []
        # Storing the running average of path lengths
        runningAvg = []
        # Store what the shortest path is
        # Stores the order of the cities, listed by their index
        bestPath = []

        # Create network, only create new network first simulation
        network, pos = CreateNetwork(nodesAmount, simiteration == 0)

        # Set best length as large
        bestL = 1000
        for i in range(maxAmountAnts + 1):
            
            # Evaporate pheromones each iteration
            for edge in network.edges():
                network.edges[edge]['pheromone'] *= (1 - evaporationRate)

            # Put ant at random node
            # Make ant go random path
            path = GetRandomPathRec([rnd.randrange(nodesAmount)])
            pathL = LengthOfPath(path)

            # Fill up currentFocus until 'runningAvgOf' is reached
            if i < runningAvgOf:
                currentFocus.append(pathL)
            else:
                # After the first iterations
                # Add the average to runningAvg
                runningAvg.append(sum(currentFocus)/len(currentFocus))
                # Add the new value to currentFocus
                currentFocus.append(pathL)
                # Remove the oldest value
                currentFocus = currentFocus[1:]

                # If the difference between the current runing average and the bestlength is 
                # within the termination percentage (5% in this case), 
                # and we've done at least 'minimumAnts' iterations,
                # Terminate
                if (runningAvg[-1] - bestL) / bestL < terminationLine and i > minimumAnts:
                    break

            # If current path is shorter than shortest path
            if pathL < bestL:
                # Store new best path
                bestL = pathL
                bestPath = path
            
            # Append current values to history lists
            bestLenHistory.append(bestL) 
            antLenHistory.append(pathL)

            # Store snapshot of pheromones at intervals
            if i % snapshotInterval == 0:
                pheroHistory.append(nx.get_edge_attributes(network, 'pheromone'))
            
            # diff, how close to best seen solution
            # Adding .001 to avoid division by zero
            diff = pathL - bestL + .001
            IncrementPheromones(path, pheromoneRate/diff)
        
        # Store each history list in lists,
        # So we can draw performance graphs on each simulation's history
        globAntLenHistory.append(antLenHistory)
        globBestLenHistory.append(bestLenHistory)
        globRunningAvgHistory.append(runningAvg)
        
        pheroHistories.append(pheroHistory)
        bestLengths.append(round(bestL, 6))
        bestPaths.append(bestPath)
        
        # Only do the animation if we're doing a single simulation
        if simulations == 1:
            DisplayNetworkAnims(pos, 0, snapshotInterval, True)
    
    # If simulating multiple times, draw each network, no animation
    if simulations != 1:
        for index in range(len(pheroHistories)):
            DisplayNetworkAnims(pos, index, snapshotInterval, False)
            
    # Draw the performance graph, for each simulation
    PerformanceGraph(globAntLenHistory, 
                     globRunningAvgHistory, 
                     globBestLenHistory)

    # Return the best paths and their lengths
    return bestLengths, bestPaths

Function calls

#Hyperparameters
nodesAmount=15

# Bias variables toward greedy and pheromone approach
distBias=2 # Increases bias toward choosing closer nodes
pheroBias=1 # Increase bias toward choosing pheromones, edges which have been traversed previously

# percentage of pheromones that evaporates each iteration
evaporationRate = .0001

# Coefficient for adding pheromones
pheromoneRate = .001

# Run this to see animation and one simulation
RunACO(nodesAmount,
       distBias,
       pheroBias,
       evaporationRate,
       pheromoneRate, 1)

You can click the slider and then use the left/right arrows to step through the process

interactive(children=(IntSlider(value=0, description='step', max=38), Output()), _dom_classes=('widget-interac…

([2.89], [[3, 0, 5, 13, 6, 14, 11, 8, 2, 10, 7, 12, 1, 9, 4]])

# How many simulations to run on the same graph
simAmount = 6

# Run this to see multiple simulations
RunACO(nodesAmount, 
       distBias, 
       pheroBias,
       evaporationRate,
       pheromoneRate, simAmount)

You can click the slider and then use the left/right arrows to step through the process

interactive(children=(IntSlider(value=0, description='step', max=14), Output()), _dom_classes=('widget-interac…

You can click the slider and then use the left/right arrows to step through the process

interactive(children=(IntSlider(value=0, description='step', max=19), Output()), _dom_classes=('widget-interac…

You can click the slider and then use the left/right arrows to step through the process

interactive(children=(IntSlider(value=0, description='step', max=9), Output()), _dom_classes=('widget-interact…

You can click the slider and then use the left/right arrows to step through the process

interactive(children=(IntSlider(value=0, description='step', max=59), Output()), _dom_classes=('widget-interac…

You can click the slider and then use the left/right arrows to step through the process

interactive(children=(IntSlider(value=0, description='step', max=16), Output()), _dom_classes=('widget-interac…

You can click the slider and then use the left/right arrows to step through the process

interactive(children=(IntSlider(value=0, description='step', max=15), Output()), _dom_classes=('widget-interac…

([3.47, 3.47, 3.47, 3.47, 3.47, 3.47],
 [[8, 2, 6, 13, 1, 11, 5, 4, 12, 7, 14, 0, 10, 3, 9],
  [3, 10, 0, 14, 7, 12, 4, 5, 11, 1, 13, 6, 2, 8, 9],
  [8, 2, 6, 13, 1, 11, 5, 4, 12, 7, 14, 0, 10, 3, 9],
  [8, 2, 6, 13, 1, 11, 5, 4, 12, 7, 14, 0, 10, 3, 9],
  [14, 0, 10, 3, 9, 8, 2, 6, 13, 1, 11, 5, 4, 12, 7],
  [8, 2, 6, 13, 1, 11, 5, 4, 12, 7, 14, 0, 10, 3, 9]])

Notes about output

Observe that we can see the length of the best path at the bottom of the output. When running multiple simulations we can see the stochastic component of this algorithm, as the final solution and the iterations required to get there varies for different smulatons on the same graph. We can see that the simulations that find a suboptimal solution also tend to be the ones that terminated early.

All line graphs above are interactive, you can select and deselect lines by clicking them in the legend. By clicking and dragging inside the graphs you can zoom in.

Explaining the algorithm

The algorithm simulates ants and how they in the real world find the best using pheromones. The concentration of pheromones is an emergent property of accumulated knowledge in the system. The core mechanic that makes this pathfinding work is that shorter paths will accumulate more pheromones as ants will walk there more frequently.

The algorithm works as follows:

Initialization:

1. Set each edge's distance attribute to the euclidian distance between its two nodes
2. Set each edge's pheromone value to 1
3. Define termination condition, maximum and mimum amount of ants to simulate

Algorithm

For each ant:

1. Put the ant at a random node
2. The ant chooses the next node to traverse depending on each edge's:
   A. Distance attribute, representing the euclidian distance to that node
   B. Pheromone concentration, represening how much this edge has been traversed and how good(short) the path it resulted in was
   C. The ant takes these two values to the power of their bias (how biased the ant should be toward each value), and then multiplies the result. $$distance^{-distBias}\times pheromone^{pheroBias} $$ This value will be calculated for each available node, and is the weighted probability of that node being selected.
3. Select a node randomly depending on their weighted probability. The ant moves to the selected node
4. Repeat 2-3 until all nodes are visited
5. Calculate the length of the ants path and the differnce between this path and the shortest path found so far (save this path length as shortest path so far, if that's the case)
6. Increase the phermone of each edge traversed by the ant, increase with reciprocal of the difference from step 5 (a small difference would be a good path, which should increase the pheromone more)
7. Take a new ant and go to step 1, repeat until out of ants

Termination condition

There are many ways one could design a termination condition. The goal of my termination condition is to correctly detect when the algorithm has "decided" upon a path, which I define as the probability of the algorithm "changing its mind" is decreasing and accellerating heavily. This event is very clear visibly in my animation, as the chosen paths edges become thicker, and all other edges practically disappear.

This is a good termination condition as running the simulation further would by definition not give a new solution, but only reinforce the one found. A negative is that we can't confirm that this will happen within a reasonable amount of time, for this reason I implemented a maximum amount of ants to simulate, as a secondary termination condition. This hyperparameter, much like the other hyperparameters, are dependent on the amount of nodes in the network, the computational time that is reasonable for the context, and the desired confidence.

When deciding on a termination condition I utilized the linegraph I produced which described the progress of the ants, this graph gave valuable insight on how to detect this event. First I considered only running for a predetermined amount of iterations only, which could be a sufficient condition depending on context, but clearly not effective as it sometimes would perform computation that has no effect on the result, and sometimes it would terminate before a path had been clearly desided upon. After examining the graph I noticed that the distribution of path-distances was "cut-off" approximately at the same time as when the desired effect could be visually seen in the animation. From this I added both the red and green line, the average distance of the paths and the shortet path found so far. With those additions it became apparent how the "deciding" event occured when a more significant portion of the ants took the best path found so far, which further reinforces it and further increases the amount of ants taking that path. When formulating the termination condition I considered:

• "when x ants in a row go on the best path", but I concluded that was to affected by random events
• "When the average range of the distribution of path-distances was cut to 75%", but it would be difficult to define and difficult to interpret how that confidently is connected to a decision being made
• "When ants taking the best path represent the fraction x of the latest n ants", I felt this would be to affected by randomization and It'd be unclear how to specify these new hyperparameters Finally I stopped on
• "When the runnning average (last 50 ants) of the distance is within 5% of the shortest path", This is an accurate proxy for the decision event, as well as being easy to implement, interpret, and cheap to check for. It's also clear how this is directly connected to more ants taking the shortest path and starting the reinforcement loop. This critical line is represented by the green dashed line in the linegraph.

Another termination condition that would be a more accurate representation of "one single path being chosen" is to see if the edges contained in the path are the only edges which are "activated", where not activated would be represented by edges having pheromone levels below some critical level. Where that critical level would be so low compared to the activated edges that they're effectively irrelevant. This would be a good termination condtion, but I judged it to be too costy to compute in each iteration, as I would have to check the levels of each edge every single iteration

Pheromone evaporation

The evaporation rate of the system is proportional to the current pheromone level, while the incrementation of pheromones is a constant value. This means that when the current pheromone levels are low, the impact of increasing pheromones will be relatively larger than the rate of evaporation. Vice versa is also true, if the pheromone levels are large the evaporation will be larger as well. Practically this means that an edge with less pheromones will, after being visited, get a more longer lasting impact than an edge that already has a lot of pheromones, there is a bias towards edges that are not visited that much, promoting any shorter paths found by random exploration. This effect is a balance against the effect that paths with more phermones will get visited a lot more. If the evaporation was not proportional, but had a constant value for decrementation, it would increase the probability that the algorithm would reinforce early solutions too heavily and settle on a local minima.

Discussion

ACO is a stochastic optimization algorithm which, simular to simulated annealing, can find the global minima by allowing for random and temporary decrease in the objective function to fall into other basins that might lead to a better local minima, or perhaps even global minima (assuming we're looking to maximize). This is preferable over greedy and naive algorithms which have no process to avoid getting stuck in a local minima.

This stochastic property of course leaves the possibility for varying results on the same graph, therefore introducing the probability of suboptimal solutions. In ACO there are many small entities, ants, having a small impact on the system probabilities, pheromones. This in combination with the fact that better paths gets more pheromone than worse paths means that the only way for a suboptimal path to get chosen is for many random events "choosing" the less probable option. If path A is 1 units longer than the best path found so far, and path B is 2 units longer, then twice as many ants would have to randomly choose Path B than A for their pheromone levels to stay the same. Only if B is randomly selected more than twice as much in such succession so that its increased pheromone levels gives it twice the probability of being selected compared to A, only then could the pheromones take over to select a suboptimal path. This issue can be mitigated by decreasing the pheromones that ants spread, requiring mor e inprobable events in a row to hit this critical value. Relevant is also the evaporation rate, with a small evaporation rate, incorrectly enforced paths will stay for longer, increasing the chance of reinforcing the bad path. Following the logic above, we can control and decrease the probability of "accidentally" reinforcing a suboptimal solution by increasing the amount of ants, decreasing their individual pheromone spread, and increasing the fraction of pheromones that are evaporated.

ACO is clearly much more effective than both a greedy best first search (https://en.wikipedia.org/wiki/Best-first_search) and a brute force approach. The greedy best first would be very fast, especially if only run a single time, but has no process to avoid getting stuck in a local minima, which also means it often does not find the optimal solution, depending on the complexity of the problem. Brute force on the other hand will guaranteed find the best solution, although as it has a time complexity of O(n!), this algorithm becomes unfeasibly slow as n increases (n being the amount of nodes in the network). Greedy best first and brute force are on the two extremes on the balance between quality of result and time complexity. ACO has a much better balance, as it quickly eliminates large parts of the solution space while keeping a broad exploration.

Greedy best first search could also get stuck in local minima which are very bad solutions. If ACO gets stuck in local minima, it will with high probability be near optimal. Since the incrementing of the pheromones is proportional to the difference of the solutions and the best solution so far, it is much easier to get out of a local minima which is far away from best so far. Local minima that have a large difference of the objective function compared to the lowest point found so far become more volatile, or unstable. This stays true if the best solution found so far is close to the global minima, which is in general the case for ACO because of how it traverses the solution space. As covered in detail by (Gómez & Barán, n.d.), one of the reasons for ACOs success in TSP is its ability narrow down the soluton space. This can loosely be explained by the fact that near-optimal solutions for the TSP would share many edges, which is in ACOs favor as it's an edge selection based algorithm. Put in more concrete words, it's highly unprobable that there's a path which is significantly better than the best path found so far, which does not share any edges. Another way to phrase it is that the solution space has a convex structure at a larger scale.

Comparison, GA and ACO

Comparing a genetic algorithm (GA) and ACO is interesting as when you look at them conceptually, they in general build on similar principles when it comes to TSP (Gómez & Barán, n.d.). A similarity is that both algorithm can be seen as working with some kind of population, which has direct and combined impact on the further state. This is clear in GA, but also in ACO if you consider the edges as individual chromosomes, subject to high elitism. They performing crossover by increasing the probability that edges connected to a "high-pheromone" edge get searched, meaning that two "high-pheromone" edges can effectively merge, by increasing the amount of ants running over their nodes, and probabilisticly favoring the edges that connect these edges. Mutation, or exploration in the solution space, is performed by the random selections of each individual ant. These similarities are of course very conceptual, the largest practical difference are how this "crossover" and "mutation" is performed. The crossover in ACO is on a local scale, while GA does crossover between two whole paths. In ACO the crossover does not make large steps from the "parents" in the solution space, instead incremental steps which favor improving objective function, the negative of this is that it's not as exploratory as the GA crossover, which can mix entire paths in different ways. The mutation is also different, in ACO it has a very frequent but small effect, while in GA it's more rare but has more extreme effects (Depends on how it's perfromed, but a common approach, switching place of two cities, has a large impact on the objective function).

It has been shown that ACO outperforms GA in Path-finding problems which have similarity to TSP. In the test performed by (Sariff & Buniyamin, 2010), ACO was more than twice as fast in finding the optimized path.

Possible improvements

There are multiple possible improvements for this algorithm. One is simply to run the algorithm multiple times with different hyperparameters, measuring the overall performance and finding the optimal hyperparameters for the specific use case. Another is simply performing the simulation in parallel, conecptually this could be like having multiple colonies of ants which are not affected by eachothers pheromones, this would decrease the probability of getting stuck in local minima (Manfrin et al., 2006). Another interesting example of an improvement is making the pheromone distribution rank-based, similar to rank-based selection in GAs, we would only allow the top $n$ ants spread pheromones, we could also make this pheromone spread proportional to the ants rank instead of its performance (Dorigo, 1999). More developed versions of ACO, and how they work, is covered by (Gómez & Barán, n.d.).

emergent properties

This algorithm relies on how the pheromone accumulation on the graph edges is an emergent property of learning between the ants. Every single ant walks pseudorandomly and sprouts pheromones in proportion to the reciprocal of distance traveled, no ant has any understanding of the overall path, they also don't learn anything as they don't adapt their behavior, they only follow the pheromones laid by other equally dumb ants. The incremental effect the pheromone has on the probabilites of following ants decisions lead to a positive feedback loop, reinforcing the edges which often take part in paths which end up short. No ant has any sense of the shortest path, but the pheromone concentration represents the collective learning of many ants and their decisions. This emergent property is exactly what we observe in the animation for the graph, where we can intuitively see how this collective learning adapts, changes it mind, has different certainty, and finally converges upon a reinforcing decision.

Bibliography

Binti Sariff, N., & Buniyamin, N. (2010). GENETIC ALGORITHM VERSUS ANT COLONY OPTIMIZATION ALGORITHM - Comparison of Performances in Robot Path Planning Application. Proceedings of the 7th International Conference on Informatics in Control, Automation and Robotics. https://doi.org/10.5220/0002892901250132

Dorigo, M. (1999, April). (PDF) ACO Algorithms for the Traveling Salesman Problem. ResearchGate. https://www.researchgate.net/publication/2771967_ACO_Algorithms_for_the_Traveling_Salesman_Problem

Gómez, O., & Barán, B. (n.d.). Relationship between Genetic Algorithms and Ant Colony Optimization Algorithms (p. Section 7.1). Retrieved March 7, 2022, from https://www.cnc.una.py/publicaciones/1_86.pdf

Manfrin, M., Birattari, M., Stützle, T., & Dorigo, M. (2006). Parallel Ant Colony Optimization for the Traveling Salesman Problem. Ant Colony Optimization and Swarm Intelligence, 224–234. https://doi.org/10.1007/11839088_20